package Solutions;

/**
 * @Classname IsUniqueLCCI
 * @Description TODO
 * @Date 2021/6/12 14:06
 * @Created by LengDanran
 * 实现一个算法，确定一个字符串 s 的所有字符是否全都不同。
 *
 * 示例 1：
 *
 * 输入: s = "leetcode"
 * 输出: false
 *
 * 示例 2：
 *
 * 输入: s = "abc"
 * 输出: true
 *
 * 限制：
 *
 *     0 <= len(s) <= 100
 *     如果你不使用额外的数据结构，会很加分。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/is-unique-lcci
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class IsUniqueLCCI {

    static class MyMap {
        private int map = 0;
        public boolean contains(char ch) {
            int value = ch - 'a' + 1;
            value = 1 << value;
            return (this.map & value) != 0;
        }
        public void put(char ch) {
            int value = ch - 'a' + 1;
            value = 1 << value;
            this.map = this.map ^ value;
        }
    }

    /***
     * 执行结果：
     * 通过
     * 显示详情
     *
     * 添加备注
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00% 的用户
     * 内存消耗：35.9 MB, 在所有 Java 提交中击败了85.32% 的用户
     *
     * 以一个'a'字符为例子：
     * 初始值：
     *         set     = 00000000 00000000 00000000 00000000 = 0
     *         value   = 00000000 00000000 00000000 00000001 = 1 = 1 << 0 = 1 << ('a' - 'a')
     * 判断是否存在，set & value:
     *     set & value = 00000000 00000000 00000000 00000000 = 0 ====>>> 'a'字符没有在set中
     * 添加一个字符 'a': set = (set ^ value):
     *     set ^ value =
     *                   00000000 00000000 00000000 00000000
     *             ^     00000000 00000000 00000000 00000001
     *             ===============================================
     *         =         00000000 00000000 00000000 00000001
     * 判断'a'是否在set中，二者按位与：
     *     set & value =
     *                   00000000 00000000 00000000 00000001
     *             &     00000000 00000000 00000000 00000001
     *             ===============================================
     *         =         00000000 00000000 00000000 00000001 ======>>>>'a'字符在set中
     *
     *
     * 作者：jason-danran0612
     * 链接：https://leetcode-cn.com/problems/is-unique-lcci/solution/yong-intlei-xing-de-zheng-shu-lai-dai-ti-1b3x/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    public boolean isUnique(String str) {
        if (str == null || str.length() < 2) return true;
        MyMap map = new MyMap();
        char[] chars = str.toCharArray();
        for (char ch : chars) {
            if (map.contains(ch)) return false;
            map.put(ch);
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(new IsUniqueLCCI().isUnique("aabc"));
    }
}
